1. Field of the Invention
The present invention relates to an apparatus for calculating matrices, in particular, for calculating multiplication of a vector by a matrix containing a large number of zero components (sparse matrices).
2. Description of the Related Art
In simulation of natural phenomena utilizing computers, it is common practice to calculate the linear transformation of vectors represented in a one-dimensional array by using a matrix represented in a two-dimensional array as a transformation matrix.
For example, the matrix calculations shown as Equations (1) and (2) are known. EQU y=Wx (1) EQU V.sup.t =u.sup.t W (2)
where x=(x.sub.1, x.sub.2, x.sub.3, . . . , x.sub.M).sup.t represents an input vector, y=(y.sub.1, y.sub.2, y.sub.3, . . . , y.sub.M).sup.t represents an output vector, W={Wji} represents a transformation matrix of N rows.times.M columns for linear transformation, u=(u.sub.1, u.sub.2, u.sub.3, . . . , u.sub.N).sup.t represents an input vector, v=(v.sub.1, v.sub.2, v.sub.3, . . . , v.sub.M).sup.t represents an output vector, and in the above-mentioned notation, (*).sup.t represents a transposed matrix of matrix * in which rows and columns are swapped.
A known matrix calculating apparatus such as a vector processor is provided with a memory for storing data representative of each element Wji of the transformation matrix W, memory device for storing calculation algorithms for calculating the product sum of the element Wji and the element of the input vector, and calculating device for executing calculations in accordance with the calculation algorithms. In calculating Equation (1), the conventional matrix calculating apparatus is adapted to calculate an output y.sub.j =(j=1, 2, . . . , N) in accordance with the following equation (3): ##EQU1##
In calculating Equation (2), the conventional matrix calculating apparatus is adapted to calculate an output v.sub.i =(i=1, 2, . . . , N) for each column in accordance with the following equation (4): ##EQU2##
The calculations of Equations (3) and (4) are diagrammatically shown in FIGS. 1 and 2, respectively.
When the above-described matrix calculations are applied to the simulation of an actual phenomenon, there is a case where a large proportion of the elements Wji of the transformation matrix W are elements of zeros (hereinafter referred to as "zero elements"). For example, in the simulation of a neural network, transmission signals which are transmitted from one group of neurons to another group of neurons may be expressed in terms of the linear transformation y=Wx, using an output from each element of transmitter as an input vector x, which utilizes the strength of connection (hereinafter referred to as "weight") from each element on the transmitter to a corresponding element on the receiver as a transformation matrix W. In this case, it is a rare case that connections are made between all the neurons of the respective groups. Rather, in many cases, the weights between the respective neurons, that is, the elements of the transformation matrix W may include a large proportion of zero elements (sparse matrix). This tendency increases as the scale of the neural network increases.
In such a case, the known calculating apparatus needs to store the elements Wji of the transformation matrix W of N rows times M columns, i.e., N rows.times.M columns by directly allocating the elements Wji for memory as real numbers N times M, i.e., N.times.M as the same as operating the matrices having a large proportion of non-zero elements, and each of multiplication and addition must be repeated N times for each matrix calculation. Consequently, unnecessary zero elements must be stored and calculated.